// 数组中有2种数出现了奇数次，其他的数都出现了偶数次
// 返回这2种出现了奇数次的数
// 测试链接 : https://leetcode.cn/problems/single-number-iii/
public class DoubleNumber {

    public static void main(String[] args) {
        int[] nums = {1,1,2,2,3,4,4,7,7,8};
        int[] ret = singleNumber(nums);
        for (int n : ret) {
            System.out.print(n+" ");
        }
    }

    public static int[] singleNumber(int[] nums) {
        int eor = 0;
        for(int e : nums) {
            eor ^= e;  //结果为两个奇数的数相异或的结果 a^b
        }

        //int rightOne = eor & (~eor + 1);
        int rightOne = eor & (-eor);  //找到这个是数二进制中最右边的第一个1
        int eorOther = 0;
        for(int i = 0; i < nums.length; i++) {
            if((nums[i] & rightOne) == 0) {
                eorOther ^= nums[i];
            }
        }
        int a = eor ^ eorOther;
        int b = eor ^ a;
        return new int[]{a,b};
    }
}
